package A_review.huawei_10_27;


public class QuickSort {

    public  int[] quickSort(int[] nums){
        if (nums.length<=1){
            return  nums;
        }
        sort(nums,0, nums.length-1);
        return  nums;
    }

    public  void sort(int[] nums,int lo,int hi){
        if (lo>=hi){
            return;
        }
        int part = findPart(nums, lo, hi);
        sort(nums,lo,part-1);
        sort(nums,part+1,hi);
    }
    public  int findPart(int[] nums,int lo,int hi ){
       int part= nums[lo];
       int j=lo+1;
       int k=hi;
       while (j<=k){
           while (j<=hi&&nums[j]<=part){
               j++;
           }
           while (k>=lo&&nums[k]>part){
               k--;
           }
           if (j>k){
               break;
           }
           swap(nums,j,k);
       }
       swap(nums,lo,k);
       return k;

    }

    public  void  swap(int[] nums,int j,int k){
        int temp=nums[j];
        nums[j]=nums[k];
        nums[k]=temp;
    }

    public static void main(String[] args) {
        QuickSort quickSortt = new QuickSort();
        int[] arr=new int[]{2,3,41,4,5,32,1,34,32,41};
        int[] ints = quickSortt.quickSort(arr);
        for (int a: ints
             ) {
            System.out.println(a);

        }
    }

}
